//
// Description: 87. 扰乱字符串
// Created by Loading on 2022/6/11.
//

#include <bits/stdc++.h>

using namespace std;

bool isScramble(string s1, string s2) {
    int n = s1.size();

    // 区间dp
    // dp[i][j][k] 表示 s1 从 i 开始，s2 从 j 开始，长度是 k 的两个子串是否扰乱
    bool dp[n][n][n + 1];
    memset(dp, false, sizeof dp);

    // 初始化
    dp[0][0][0] = true;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // 长度为 1 的子串
            if (s1[i] == s2[j]) {
                dp[i][j][1] = true;
            }
        }
    }

    // 区间dp，从长度开始枚举
    for (int len = 2; len <= n; ++len) {
        // 枚举 s1 s2 下标
        for (int i = 0; i + len - 1 < n; ++i) {
            for (int j = 0; j + len - 1 < n; ++j) {
                // 枚举子长度
                for (int k = 1; k < len; ++k) {
                    // 子串顺序不变时，左侧对应左侧，右侧对应右侧
                    dp[i][j][len] |= (dp[i][j][k] && dp[i + k][j + k][len - k]);
                    // 子串顺序变化时，左侧对应右侧，右侧对应左侧
                    dp[i][j][len] |= (dp[i][j + len - k][k] && dp[i + k][j][len - k]);
                    if (dp[i][j][len]) {
                        break;
                    }
                }
            }
        }
    }

    return dp[0][0][n];
}

int main() {
    string s1 = "abcdbdacbdac";
    string s2 = "bdacabcdbdac";

    auto res = isScramble(s1, s2);

    cout << res << endl;

    return 0;
}